iT邦幫忙

2021 iThome 鐵人賽

DAY 11
1
自我挑戰組

每日攝取一點資料結構和演算法系列 第 11

Day11:[資料結構]Binary Tree - 二元樹

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20210911/20128604Pk2VlP7hZN.jpg

想必大家在刷leetcode時候,刷到特定的題目的時候都曾經看過這樣的圖片,這就是Binary tree,但在認識Binary tree之前,讓我們先來認識tree這種資料結構吧!

https://ithelp.ithome.com.tw/upload/images/20210911/20128604rUc7Tvt2Wt.png
圖片來源:101. Symmetric Tree

Tree

是一種抽象的資料結構,由一個以上的節點所組成,每個節點可以有多個子節點,最頂端的根節點稱為root ,最下面的層級的節點稱為leaves(2, 1, 7 …)
https://ithelp.ithome.com.tw/upload/images/20210911/20128604ahAn44zETi.png

圖片來源:working-with-trees

而節點與節點之間的關係名詞可以參考下圖
https://ithelp.ithome.com.tw/upload/images/20210911/20128604W3ALW1Ezde.png

圖片來源:understanding-binary-search-trees-4d90

  • Root - 根節點,最上層的節點
  • Edge- 節點與節點之間的連結
  • Parent - 父節點,與節點相鄰的上層節點
  • Children - 子節點,與節點相鄰的下層節點
  • Siblings - 兄弟節點,層級在同一層,而且擁有共同的父節點
  • Leaf nodes - 葉子節點,沒有子節點的節點
  • Subtree - 子樹,該節點以及其左右子節點
  • Height - 樹的高度,可以解讀為樹有幾層

Binary Tree(二元樹)

每個節點的子節點最少0個,最多2個 ,每個節點會紀錄三種資料

  • 自己本身的值
  • left-child,左子節點
  • right-child,右子節點

https://ithelp.ithome.com.tw/upload/images/20210911/20128604RDWVJAD8jY.png
圖片來源:Binary Tree

與一般樹的比較如下,Binary Tree每個節點最多就是兩個子節點
https://ithelp.ithome.com.tw/upload/images/20210911/20128604MKhG4jgvcR.png

圖片來源:difference-between-general-tree-and-binary-tree

Binary Tree的種類

https://ithelp.ithome.com.tw/upload/images/20210911/20128604XFQ9KG13c6.png

圖片來源:5-types-of-binary-tree-with-cool-illustrations

full

  • 所有的leaf node都在同一個層級
  • 每個節點的子節點為0個或是2個

Complete

  • 除了最後一層leaf node之外,每層都是填滿的狀態
  • 所有的leaf node都會向左靠攏,因此leaf nodes有可能會沒有右邊的兄弟節點

Degenerate

  • 每個節點只會有一個右子節點或是左子節點

Perfect

  • 所有的leaf node都在同一個層級
  • 除了leaf node之外,每個節點都有兩個子節點

Balance

  • 左子樹和右子樹的層級相差不超過1

Skewed 

  • 每個節點固定只有右子節點或左子節點,如下圖
    https://ithelp.ithome.com.tw/upload/images/20210911/20128604QzOrm09F0M.png
    Skewed Binary Tree,圖片來源:binary-tree

Binary Search Tree(縮寫BST) - 二元搜尋樹

具有Binary Tree的特性,每個節點的子節點不超過2個,除此之外,左邊的子節點必定小於根節點,右邊的子節點必定大於根節點,因此整棵樹最左邊的節點必定是最小的,最右邊的節點必定是最大的,也因為Binary Search Tree這樣的特性,所以不管是新增節點、刪除節點、搜尋節點的時間複雜度都是O(log n)。

https://ithelp.ithome.com.tw/upload/images/20210911/20128604yjrvtv9EWu.jpg
圖片來源:implementing-binary-search-tree

用js實作出Binary Search Tree

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
        this.queue = [];
    }
    insertNode(value) {
        let current = new TreeNode(value);
        let target = null;
        let nowPos = this.root;
        while (nowPos !== null) {
            target = nowPos;
            if (current.value < nowPos.value) {
                nowPos = nowPos.left;
            } else {
                nowPos = nowPos.right;
            }
        }
        if (target === null) {
            this.root = current;
        } else if (current.value < target.value) {
            target.left = current;
        } else {
            target.right = current;
        }
    }
}

let tree = new BinarySearchTree();
tree.insertNode(10);
tree.insertNode(8);
tree.insertNode(11);
tree.insertNode(5);
tree.insertNode(9);
tree.insertNode(15);
tree.insertNode(2);
tree.insertNode(19);
tree.insertNode(13);

如果consolo.log(tree)可以看到我們成功用物件模擬出一顆Binary Search Tree
https://ithelp.ithome.com.tw/upload/images/20210911/20128604Qu0wY103N4.png

Binary Heaps - 二元堆積

Binary Heaps又分為Min-Heaps 和 Max-Heaps,適合用來找最小值或最大值

  • Min-Heaps :每個節點都會比自己的子節點還小,因此根節點會是最小值
  • Max-Heaps:每個節點都會比自己的子節點還大,因次根節點會是最大值

https://ithelp.ithome.com.tw/upload/images/20210911/20128604c2fTCGexpj.png
圖片來源:heap-data-structure

關於Heap Tree的實作會在之後的Heap Sort文章中介紹

參考資料: understanding-binary-search-trees

full-binary-tree


上一篇
Day10: [資料結構] Graph - 圖
下一篇
Day12:[資料結構]Binary Tree -  Traversal
系列文
每日攝取一點資料結構和演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言